package com.cat.dataStructure02;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-spending-after-buying-items/
 * @create 2025/10/6 21:09
 * @since JDK17
 */

public class Solution04 {
    public long maxSpending(int[][] values) {
        long ans = 0;
        int n = values.length, m = values[0].length, tot = m * n;
        int[] idx = new int[n];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            idx[i] = m - 2;
            heap.add(new int[] { values[i][m - 1], i });
        }
        for (int i = 1; i <= m * n; i++) {
            var x = heap.poll();
            ans += (long) i * x[0];
            if (idx[x[1]] >= 0) {
                heap.add(new int[] { values[x[1]][idx[x[1]]--], x[1] });
            }
        }

        return ans;
    }
}
